#include "heur.h"




/* Calcula o custo de uma permutacao */
int calcCost(const Job *jobs, const int nJobs) {
    int acc1, acc2, total, i;

    total = 0;
    acc1 = 0;
    acc2 = 0;

    for (i = 0; i < nJobs; i++) {
        acc1 += jobs[i].task1;
        acc2 = max(acc2, acc1) + jobs[i].task2;
        total += acc2;
    }

    return total;
}


/* Funcao que resolve o tempo minimo de execucao */
void johnson(Job *jobs, const int nJobs) {
    int begin, end, mid, i;
    Job tmp;


    /* realiza a particao do vetor */
    begin = 0;
    end = nJobs - 1;
    while (begin < end) {
        if (jobs[begin].task1 >= jobs[begin].task2) {
            /* inverte */
            while ((begin < end) && (jobs[end].task1 >= jobs[end].task2)) {
                end--;
            }
            
            tmp = jobs[begin];
            jobs[begin] = jobs[end];
            jobs[end] = tmp;

            end--;
        }
        
        begin++;
    }

    /* localiza a divisao do vetor */
    mid = 0;
    while ((mid < nJobs) && (jobs[mid].task1 < jobs[mid].task2)) {
        mid++;
    }


    /* DEBUG: imprime a particao realizada */
    if (DEBUG) {
        fprintf(stderr, "vetor particionado (%d):\n", mid);
        for (i = 0; i < nJobs; i++) {
            fprintf(stderr, "%d: job%d (%d, %d)\n", i, jobs[i].id + 1, 
                    jobs[i].task1, jobs[i].task2);
        }
        fprintf(stderr, "\n");
    }
    
    
    /* ordena */
    qsort(&jobs[0],   mid,       sizeof(Job),
            (int(*)(const void *, const void *))firstSetcmp);
    qsort(&jobs[mid], nJobs-mid, sizeof(Job),
            (int(*)(const void *, const void *))secondSetcmp);


    /* DEBUG: imprime o vetor ordenado */
    if (DEBUG) {
        fprintf(stderr, "vetor ordenado:\n");
        for (i = 0; i < nJobs; i++) {
            fprintf(stderr, "%d: job%d (%d, %d)\n", i, jobs[i].id + 1, 
                    jobs[i].task1, jobs[i].task2);
        }
        fprintf(stderr, "\n");
    }
}


/* Funcao que acha o minimo local */
void hillClimbing(Job *jobs, const int nJobs) {
    int bestI, bestJ, custo, least, prox, i, j;
    Job tmp;
    struct itimerval timer;


    /* enquanto houver vizinho melhor */
    do {
        custo = calcCost(jobs, nJobs);
        least = custo;

        /* calcula os vizinhos */
        for (i = 0; i < nJobs; i++) {
            for (j = i+1; j < nJobs; j++) {
                /* troca os jobs i e j */
                tmp = jobs[i];
                jobs[i] = jobs[j];
                jobs[j] = tmp;

                prox = calcCost(jobs, nJobs);

                /* verifica qualidade */
                if (prox < least) {
                    least = prox;
                    bestI = i;
                    bestJ = j;
                }

                /* arruma o vetor */
                tmp = jobs[i];
                jobs[i] = jobs[j];
                jobs[j] = tmp;
            }
        }

        /*  o melhor */
        if (least < custo) {
            tmp = jobs[bestI];
            jobs[bestI] = jobs[bestJ];
            jobs[bestJ] = tmp;
        }
    
        getitimer(ITIMER_REAL, &timer);

    } while ((least < custo) && (timer.it_value.tv_sec > 0));
}


/* Funcao que gera uma permutacao aleatoria de jobs */
void shuffleJobs(Job *jobs, const int nJobs) {
    Job tmp;
    int i, j;

    srand(time(NULL));

    for (i = 0; i < nJobs; i++) {
        /* i <= j < n*/
        j = rand() % (nJobs-i)   + i;

        tmp = jobs[i];
        jobs[i] = jobs[j];
        jobs[j] = tmp;
    }
}


/* Funcao que aplica a heuristica GRASP */
void grasp(Job *jobs, const int nJobs, const int maxExecTime) {
    Job *bestperm, *tmpperm;
    int bestvalue, tmpvalue, i;
    struct itimerval timer;


    /* inicializacao */
    bestperm = (Job*)memAlloc(sizeof(Job) * nJobs);
    tmpperm = (Job*)memAlloc(sizeof(Job) * nJobs);
    for (i = 0; i < nJobs; i++) {
        bestperm[i] = jobs[i];
        tmpperm[i] = jobs[i];
    }
    bestvalue = calcCost(bestperm, nJobs);

    /* controle de tempo de execucao */
    getitimer(ITIMER_REAL, &timer);

    i = 0;
    while((i < nJobs*nJobs*nJobs) && (timer.it_value.tv_sec > 0)) {
        /* estado aleatorio */
        shuffleJobs(tmpperm, nJobs);

        /* busca local */
        hillClimbing(tmpperm, nJobs);
        tmpvalue = calcCost(tmpperm, nJobs);

        /* verifica solucao */
        if (tmpvalue < bestvalue) {
            for (i = 0; i < nJobs; i++) {
                bestperm[i] = tmpperm[i];
            }
            bestvalue = tmpvalue;
        }
        i++;
        getitimer(ITIMER_REAL, &timer);
    }

    /* melhor solucao */
    for (i = 0; i < nJobs; i++) {
        jobs[i] = bestperm[i];
    }

    free(bestperm);
    free(tmpperm);
}


/* Funcao principal */
int main(int argc, char *argv[]) {

    FILE *inst, *param;
    Job *jobs, *heur1, *heur2, *heur3, *heur4, *tmp;
    int nJobs, i, valor, valor1, valor2, valor3, valor4;
    int maxNodes, maxExecTime;
    struct itimerval timer;


    /* verifica o uso */
    if (argc != 2) {
        fprintf(stderr, "uso: bnb arq_instancia\n");
        exit(EXIT_FAILURE);
    }

    /* le o arquivo param */
    param = fopen(PARAM_PATH, "r");
    fscanf(param, "%d %d", &maxNodes, &maxExecTime);
    fclose(param);

    /* le a entrada */
    inst = openFile(argv[1], "r");
    fscanf(inst, "%d", &nJobs);
    jobs = (Job*)memAlloc(sizeof(Job) * nJobs);
    for (i = 0; i < nJobs; i++) {
        jobs[i].id = i;
        fscanf(inst, "%d %d", &jobs[i].task1, &jobs[i].task2);
    }
    fclose(inst);


    /* DEBUG: imprime a entrada */
    if (DEBUG) {
        fprintf(stderr, "entrada:\n");
        for (i = 0; i < nJobs; i++) {
            fprintf(stderr, "job%d: %d %d\n", jobs[i].id+1, jobs[i].task1, jobs[i].task2);
        }
        fprintf(stderr, "\n");
    }


    /* gera os vetores para heuristica */
    heur1 = (Job*)memAlloc(sizeof(Job) * nJobs);
    heur2 = (Job*)memAlloc(sizeof(Job) * nJobs);
    heur4 = (Job*)memAlloc(sizeof(Job) * nJobs);
    for (i = 0; i < nJobs; i++) {
        heur1[i] = jobs[i];
        heur2[i] = jobs[i];
        heur4[i] = jobs[i];
    }


    /* aplica as heuristicas */
    setTimer(maxExecTime);
    johnson(heur1, nJobs);
    qsort(heur2, nJobs, sizeof(Job), (int(*)(const void *, const void *))totalTimecmp);
    valor1 = calcCost(heur1, nJobs);
    valor2 = calcCost(heur2, nJobs);

    if (DEBUG) {
        fprintf(stderr, "+ jonhson:\t");
        for (i = 0; i < nJobs; i++) {
            fprintf(stderr, "%d ", heur1[i].id + 1);
        }
        fprintf(stderr, "(%d)\n", valor1);

        fprintf(stderr, "+ tempo medio:\t");
        for (i = 0; i < nJobs; i++) {
            fprintf(stderr, "%d ", heur2[i].id + 1);
        }
        fprintf(stderr, "(%d)\n", valor2);
    }

    /* utiliza a melhor heuristica no hill climbing */
    if (valor1 < valor2) {
        heur3 = heur1;
        free(heur2);
    } else {
        heur3 = heur2;
        free(heur1);
    }

    /* hillclimbing */
    hillClimbing(heur3, nJobs);
    valor3 = calcCost(heur3, nJobs);

    if (DEBUG) {
        fprintf(stderr, "+ hill climbing:\t");
        for (i = 0; i < nJobs; i++) {
            fprintf(stderr, "%d ", heur3[i].id + 1);
        }
        fprintf(stderr, "(%d)\n", valor3);
    }


    /* grasp */
    grasp(heur4, nJobs, maxExecTime);
    valor4 = calcCost(heur4, nJobs);


    /* retorna apenas a melhor */
    tmp = jobs;
    if (valor3 < valor4) {
        jobs = heur3;
        free(heur4);
    } else {
        jobs = heur4;
        free(heur3);
    }
    free(tmp);
    valor = calcCost(jobs, nJobs);


    /* imprime a saida */
    getitimer(ITIMER_REAL, &timer);
    printf("* heuristica aplicada em %ld segundos\n",
            maxExecTime - timer.it_value.tv_sec);
    printf("> melhor solucao encontrada: ");
    for (i = 0; i < nJobs; i++) {
        printf("%d ", jobs[i].id + 1);
    }
    printf("(%d)\n", valor);
    
    
    /* libera a memoria */
    free(jobs);

    return EXIT_SUCCESS;

}

